package com.demo.java.OD451_500.OD466;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【最小矩阵宽度(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146353726
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取矩阵的行数和列数
        int rows = scanner.nextInt(), cols = scanner.nextInt();
        int[][] matrix = readMatrix(scanner, rows, cols);  // 读取矩阵
        int lenTarget = scanner.nextInt();  // 目标数组的长度
        int[] targetArray = readArray(scanner, lenTarget);  // 读取目标数组

        // 寻找最小的列宽
        int minWidth = findMinWidth(matrix, targetArray);
        System.out.println(minWidth == Integer.MAX_VALUE ? -1 : minWidth);  // 输出结果

        scanner.close();
    }

    // 读取矩阵
    public static int[][] readMatrix(Scanner scanner, int rows, int cols) {
        int[][] matrix = new int[rows][cols];
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                matrix[i][j] = scanner.nextInt();
        return matrix;
    }

    // 读取目标数组
    public static int[] readArray(Scanner scanner, int length) {
        int[] array = new int[length];
        for (int i = 0; i < length; i++)
            array[i] = scanner.nextInt();
        return array;
    }

    // 寻找最小列宽
    public static int findMinWidth(int[][] matrix, int[] targetArray) {
        int minWidth = Integer.MAX_VALUE, cols = matrix[0].length;
        // 遍历所有列区间
        for (int left = 0; left < cols; left++) {
            for (int right = left; right < cols; right++) {
                if (isSubarrayFound(matrix, targetArray, left, right))
                    minWidth = Math.min(minWidth, right - left + 1);  // 更新最小宽度
            }
        }
        return minWidth;
    }

    // 判断在当前列范围内，目标数组的所有元素是否都出现
    public static boolean isSubarrayFound(int[][] matrix, int[] targetArray, int leftBound, int rightBound) {
        int[] countArray = new int[1001];  // 计数数组，用来记录当前列范围内每个数字的出现次数
        // 遍历矩阵中的每个元素，并在当前列范围内更新计数数组
        for (int[] row : matrix)
            for (int j = leftBound; j <= rightBound; j++)
                countArray[row[j]]++;

        // 检查每个目标数组的元素是否满足出现次数
        for (int num : targetArray)
            if (countArray[num] < countOccurrences(targetArray, num))  // 不满足则返回false
                return false;
        return true;  // 满足条件返回true
    }

    // 计算目标数组中某个数字出现的次数
    public static int countOccurrences(int[] arr, int num) {
        int count = 0;
        for (int i : arr)
            if (i == num)
                count++;
        return count;
    }
}